package com.lw.leetcode.binary.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * binay
 * 1552. 两球之间的磁力
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/26 9:49
 */
public class MaxDistance1552 {

    public static void main(String[] args) {
        MaxDistance1552 test = new MaxDistance1552();

        // 3
//        int[] arr = {1, 2, 3, 4, 7};
//        int m = 3;

        // 999999999
        int[] arr = {5, 4, 3, 2, 1, 1000000000};
        int m = 2;

        int i = test.maxDistance(arr, m);
        System.out.println(i);

    }

    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int length = position.length;
        int st = 1;
        int end = (position[length - 1] - position[0]) / (m - 1);
        while (st < end) {
            int mid = st + ((end - st + 1) >> 1);
            int count = 1;
            int next = position[0] + mid;
            for (int i = 1; i < length; i++) {
                if (position[i] >= next) {
                    next = position[i] + mid;
                    count++;
                }
            }
            if (count < m) {
                end = mid - 1;
            } else {
                st = mid;
            }
        }
        return st;
    }

}
